package com.practice.niuke.new_direct_basics.class06;

import java.util.*;

/**
 * 拓扑排序算法
 * 适用范围： 要求有向图， 且有入度为0的节点， 且没有环
 */
public class Code03_TopologySort {

	/**
	 * 拓扑排序，要求是有向无环图（directed graph and no loop）
	 * @param graph
	 * @return
	 */
	public static List<Node> sortedTopology(Graph graph) {
		// inMap表示某一个节点它还剩多少入度，
		// key：某一个node
		// value：剩余的入度
		HashMap<Node, Integer> inMap = new HashMap<>();
		// 入度为0的点，才能进这个队列
		Queue<Node> zeroInQueue = new LinkedList<>();
		for (Node node : graph.nodes.values()) {
			inMap.put(node, node.in);
			// 将入度为0的点放入队列
			if (node.in == 0) {
				zeroInQueue.add(node);
			}
		}
		// 拓扑排序的结果，依次加入result
		List<Node> result = new ArrayList<>();
		// zeroInQueue（存放入度为0的节点的队列）不为空时
		while (!zeroInQueue.isEmpty()) {
			// 从zeroInQueue中弹出一个节点cur
			Node cur = zeroInQueue.poll();
			// 将cur节点放入result
			result.add(cur);
			// 相当于在源图中，去掉cur节点以及其发散出去的边。
			for (Node next : cur.nexts) {
				inMap.put(next, inMap.get(next) - 1);
				// 去掉cur节点发散出去的边后，
				// 如果发现某个节点的入度变为0，就加入到zeroInQueue队列。
				if (inMap.get(next) == 0) {
					zeroInQueue.add(next);
				}
			}
		}
		return result;
	}
}
